using System;
using System.Collections.Generic;
using System.Text;
using LispLib;

namespace GeneticAlgorithm.CP3.ParseTree
{
    class Crossover
    {
        public static Individual<Interpreter.Pair, Interpreter.Pair> A(params Individual<Interpreter.Pair, Interpreter.Pair>[] parents)
        {
            // NOTE this crossover does not swap root(top most) node in the tree

            // duplicate genotype of one of the parent to be used by the child
            Interpreter.Pair genotype = Duplicate(parents[0].Genotype);

            // find all the connectable points in parents' parse tree
            Interpreter i = new Interpreter();
            List<Interpreter.Pair> p1List = new List<Interpreter.Pair>();
            Flatten(genotype, p1List, i);
            List<Interpreter.Pair> p2List = new List<Interpreter.Pair>();
            Flatten(parents[1].Genotype, p2List, i);

            // randomly pick 2 connectable points in parents' parse tree, and connect them
            Interpreter.Pair p1Point = p1List[Global.random.Next(0, p1List.Count)];
            Interpreter.Pair p2Point = p2List[Global.random.Next(0, p2List.Count)];
            p1Point.car_ = p2Point.car_;

            return new Individual(genotype, parents);  
        }

        public static Interpreter.Pair Duplicate(Interpreter.Pair original)
        {
            // HACK should use a enumerator instead of parsing expression strings
            int pos = 0;
            string expression = original.ToString();
            return Interpreter.ReadOneExpr(expression, ref pos, expression.Length) as Interpreter.Pair;
        }

        /// <summary>
        /// Recursively go through each node in the parse tree, find connectable node for crossover
        /// and add them to the flattened list.
        /// </summary>
        /// <param name="tree">Lisp parse tree</param>
        /// <param name="list">list used to store nodes from the Lisp parse tree</param>
        public static void Flatten(Interpreter.Pair tree, List<Interpreter.Pair> list, Interpreter i)
        {
            // recurse the header and rest part
            Interpreter.Pair car = tree.car_ as Interpreter.Pair;
            if (car != null)
            {
                // a node with car's car that's a operator is swappable
                try
                {
                    Object o = i.Globals.Get(car.car_.ToString(), i.Globals);
                    if (o != null)
                    {
                        list.Add(tree);
                    }
                }
                catch (Exception)
                {
                }
                
                Flatten(car, list, i);
            }
            else if (Interpreter.IsNumericType(tree.car_.GetType()))
            {
                list.Add(tree);
            }
            else
            {
                try
                {
                    i.Globals.Get(tree.car_.ToString(), i.Globals);
                }
                catch (Exception e)
                {
                    list.Add(tree);
                }
            }

            if (tree.cdr_ == null)
            {
                return;
            }

            Interpreter.Pair cdr = tree.cdr_ as Interpreter.Pair;
            if (cdr != null)
            {
                Flatten(cdr, list, i);
            }
        }
    }
}
